// 2010-03-31 yxh
// a sorted list, if reverse = false(default), in increasing order;
// else in decreasing order
// T must has methods and overwrite "<", ">", "==", "+=" operator
#ifndef SOTERDLIST_H
#define SOTERDLIST_H
#define NULL 0

#include "Compare.h"

//using std::list;
template <class T>
class ListNode {
  public:
    ListNode() : nextp(NULL) {}
    ListNode(T node) : node(node), nextp(NULL) {}
    //    ListNode<T>* next() {return nextp;}
    T node;
    ListNode<T>* nextp;
};

template <class T>
class SortedList {
  public:
    SortedList(bool reverse = false);

    bool empty() { return head->nextp == NULL; }

    // return the first value pointer
    ListNode<T>* begin() { return head->nextp; }

    // add a elements with value 'node' to list
    void add(const T& node);

    // remove all elements '==' to node
    bool remove(const T& node);

    // remove elements if pr(node) is true
    template <class Predicate>
    void remove_if(Predicate pr);

    // combine elements in li to this
    // then li will be discard
    void combine(SortedList<T>& li);

    // just discard list struct, not list elements
    void discard();
    
    ~SortedList();

    // print all elements in the list
    void print();

    // a functional object decide the order of elements
    Compare<T>* compare;
  private:
    // find the first element after pre1, which is greater or equal to p2
    // called by combine()
    ListNode<T>* find_ge(ListNode<T>* p2, ListNode<T>* pre1);

  private:
    // the element before first element
    ListNode<T>* head;
    // the last element, optional member
    //only take use for effecient, not functional
    ListNode<T>* end;  

};
#endif
